﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace NumberOfConnectedPartsInGraph
{
    class Program
    {
        static int[,] graph = { {0, 0, 0, 0},
                                {0, 0, 1, 0},
                                {0, 0, 0, 0},
                                {0, 0, 0, 0}};

        static void Main(string[] args)
        {
            Console.WriteLine("Total number of connected part = {0}", CalculateConnectedParts(graph));
            Console.ReadLine();
        }

        static int CalculateConnectedParts(int[,] graph)
        {
            int count = 0;
            int numberOfNodes = graph.GetLength(0);
            int i = 0;

            List<int> nodeSet = new List<int>();
            
            for (i = 0; i < numberOfNodes; i++)
            {
                nodeSet.Add(i);
            }

            while (nodeSet.Count > 0)
            {
                count++;

                int nodeToRemove = nodeSet.ElementAt(0);

                Queue<int> workQueue = new Queue<int>();

                workQueue.Enqueue(nodeToRemove);

                while (workQueue.Count > 0)
                {
                    int curr = workQueue.Dequeue();
                    nodeSet.Remove(curr);

                    for (i = 0; i < numberOfNodes; i++)
                    {
                        if ((graph[i, curr] == 1) ||
                            (graph[curr, i] == 1))
                        {
                            if (nodeSet.Contains(i))
                            {
                                workQueue.Enqueue(i);
                            }
                        }
                    }
                }
            }


            return count;
        }
    }
}
